package search.binarysearch;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/24 14:32
 * @Description 二分查找
 */
public class BinarySearch {

    private BinarySearch(){


    }

    //非递归实现二分查找法
    public static <E extends Comparable<E>> int search (E[] data,E target){
        int l= 0, r=data.length-1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(data[mid].compareTo(target)==0){
                return mid;
            }
            if(data[mid].compareTo(target)<0){
                l = mid+1;
            }else{
                r= mid -1;
            }
        }
        return -1;
    }


    //递归实现二分查找法
    public static <E extends Comparable<E>> int searchR (E[] data,E target){
        return searchR(data,0,data.length-1,target);
    }

    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r,E target){

        if(l>r){
            return -1;
        }
        int mid = l+(r-l)/2;
        if(data[mid].compareTo(target)==0){
            return mid;
        }
        if(data[mid].compareTo(target)<0){
            l = mid+1;
            return searchR(data,l,r,target);
        }
        if(data[mid].compareTo(target)>0){
            r= mid -1 ;
            return searchR(data,l,r,target);
        }
        return -1;
    }

    //leetcode  875
    public int minEatingSpeed(int[] piles, int h) {

        int l = 1,r = Arrays.stream(piles).max().getAsInt();
        while(l<r){
            int mid = l + (r-l)/2;
            if(eatingTime(piles,mid)<=h){
                r = mid ;
            }else{
                l = mid + 1;
            }
        }
        return r;
    }

    private int eatingTime(int[] piles, int mid) {
        int h = 0;
        for (int pile : piles) {
            h += pile % mid == 0 ? pile/mid : pile/mid +1;
        }
        return h;
    }

    //leetcode  1011
    public static int shipWithinDays(int[] weights, int days) {
        int  l = weights[weights.length-1],r = Arrays.stream(weights).sum();
        while(l<r){
            System.out.println(l+":"+r);
            int mid = l + (r-l)/2;
            if(bigestWeight(weights,mid)<=days){
                r = mid ;
            }else{
                l = mid + 1;
            }
        }
        return r;
    }

    private static int bigestWeight(int[] weights, int mid) {
        int j = 0;
        int n = 0;
        for (int i = 0; i < weights.length; i++) {
            if(j+weights[i]<=mid){
                j+=weights[i];
            }else{
                j = weights[i];
                n++;
            }
        }
        // 最后还要做一次 res ++，因为在这里 cur 肯定不为零，还记录着最后一天需要运送的货物重量
        // 最后一天，不管走哪个if，总会有剩下的j，这个j都在最后一天运完，所以要加到 res 中，所以 res ++
        n++;
        return n;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int i = shipWithinDays(arr, 5);
        System.out.println(i);
    }
}
